import javax.lang.model.util.Elements;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
    static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val){
            this.val=val;
        }
    }
    //创建一个二叉树；
    public TreeNode createTree() {
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(5);
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(7);
        TreeNode H = new TreeNode(8);

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }
    //判断一棵树是不是平衡二叉树；
    public boolean pingHengTree(TreeNode root){
        if(root==null){
            return true;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
           TreeNode cur=queue.poll();
            if(cur==null){
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while(!queue.isEmpty()){
            TreeNode nm=queue.peek();
            if(nm!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }
//寻找两个结点的公共祖先；
    //方法一：
    public TreeNode findZuXian( TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
        if(p==root||q==root){
            return p;
        }
        TreeNode left=findZuXian(root.left,p,q);
        TreeNode right=findZuXian(root.right,p,q);
        if(left!=null&&right!=null){
            return root;
        }else if(left!=null){
            return left;
        }else if(right!=null){
            return right;
        }
        return null;
    }
//方法二：
    public TreeNode findZuXian2(TreeNode root,TreeNode p,TreeNode q){
        if(root==null){
            return null;
        }
        Stack<TreeNode> stack1=new Stack<>();
        Stack<TreeNode> stack2=new Stack<>();
        getTreeNode(root,p,stack1);
        getTreeNode(root,q,stack2);
        int size1=stack1.size();
        int size2= stack2.size();
        int size=size2-size1;
        if(size<0){
            size=size1-size2;
            while(size!=0){
                stack1.pop();
                size--;
            }
        }else{
            while(size!=0){
                stack2.pop();
                size--;
            }
        }
        while(!stack1.isEmpty()&&!stack2.isEmpty()){
            TreeNode top1=stack1.peek();
            TreeNode top2=stack2.peek();
            if(top1==top2){
                return top1;
            }else{
                stack1.pop();
                stack2.pop();
            }
        }
        return null;
    }
    public boolean getTreeNode(TreeNode root,TreeNode node,Stack<TreeNode> stack){
        if(root==null||node==null){
            return false;
        }
        stack.push(root);
        if(root==node){
            return true;
        }
        boolean flg1=getTreeNode(root.left,node,stack);
        if(flg1){
            return true;
        }
        boolean flg2=getTreeNode(root.right,node,stack);
        if(flg2){
            return true;
        }
        stack.pop();
        return false;
    }
    //根据中序遍历和先序遍历结果创建二叉树；
    public TreeNode createnm(int[] preOrder,int[] middleOrder){
        return createnmSon(preOrder,middleOrder,0,middleOrder.length-1);
    }
    public int preIndex=0;
    public TreeNode createnmSon(int[] preOrder,int[] middleOrder,int begin,int end){
        if(begin>end){
            return null;
        }
        TreeNode root=new TreeNode(preOrder[preIndex]);
        preIndex++;
        int rootIndex=findRootIndex(middleOrder,begin,end,preOrder[preIndex]);
        preIndex++;
       root.left=createnmSon(preOrder,middleOrder,begin,rootIndex-1);
       root.right=createnmSon(preOrder,middleOrder,rootIndex-1,end);
        return root;
    }
    public int findRootIndex(int[] middleOrder,int begin,int end,int key){
        for(int i=begin;i<=end;i++){
            if(middleOrder[i]==key){
                return i;
            }
        }
        return -1;
    }
//根据二叉树输出规定的字符串
// ；
    StringBuilder stringBuilder=new StringBuilder();
    public String getString (TreeNode root){

        if(root==null){
            stringBuilder.toString();
        }
        getStringSon(root,stringBuilder);
        return stringBuilder.toString();
    }
    public void getStringSon(TreeNode root,StringBuilder stringBuilder){
        if(root==null){
            return;
        }
        stringBuilder.append(root.val);
        if(root.left!=null){
            stringBuilder.append("(");
            getStringSon(root.left,stringBuilder);
            stringBuilder.append(")");
        }else{
            if(root.right==null){
                return;
            }else{
                stringBuilder.append("()");
            }
        }
        if(root.right!=null){
            stringBuilder.append("(");
            getStringSon(root.right,stringBuilder);
            stringBuilder.append(")");
        }else{
            return;
        }
    }
//前序遍历的非递归方法；
    public void preOrder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                System.out.print(cur.val+" ");
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            cur=top.right;
        }
    }
    //中序遍历的非递归实现；
    public void middleOrder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);;
                cur=cur.left;
            }
            TreeNode top=stack.pop();
            System.out.print(top.val+" ");
            cur=top.right;
        }
    }
//后序遍历的非递归方法；
    public void LastOrder(TreeNode root){
        if(root==null){
            return;
        }
        Stack<TreeNode> stack=new Stack<>();
        TreeNode cur=root;
        TreeNode prev=null;
        while(cur!=null||!stack.isEmpty()){
            while(cur!=null){
                stack.push(cur);
                cur=cur.left;
            }
            TreeNode top=stack.peek();
            if(top.right==null||top.right==prev){
                stack.pop();
                System.out.print(top.val+" ");
                prev=top;
            }else{
                cur=top.right;
            }
        }
    }
    public void postOrder1(TreeNode root) {
        if(root == null) {
            return;
        }
        postOrder1(root.left);
        postOrder1(root.right);
        System.out.print(root.val+" ");
    }

}
